\section{Problema 1}

\subsection{Introducci\'on}
En este problema, dado un ascensor con una capacidad de  movimientos limitada,
como si fuera la cantidad de energia restante, tenemos que calcular la cantidad
m\'axima de personas que puede bajar el ascensor a la planta baja antes de
quedarse sin energ\'ia.

Se nos informa  cu\'anta gente hay en cada piso esperando para bajar a la
planta baja, y la capacidad de la cabina en n\'umero de personas.

Adem\'as sabemos que el ascensor s\'olo se detiene para permitir el ingreso de
personas esperando en los pisos o el egreso en planta baja. 
Las personas s\'olo ingresan en el ascensor al detenerse y mientras haya
capacidad en la cabina.

	   
\subsection{Pseudoc\'odigo}
En el archivo \textbf{Ej1.java} podremos encontrar la clase "EJ1" con todas las funciones aqui mencionadas y vistas en forma de pseudocodigo.
Decidimos mostrar las funciones mas importantes e interesantes para la resolucion del ejercicio.

\begin{itemize}
 \item  \textit{maxPeople}: Esta función es recursiva, busca entre los posibles candidatos a ser el resultado, los que realmente tienen posibilidades,mejor dicho, si pensamos a la solucion como dependiendo de la cantidad maxima de personas en el edificio, podemos pararnos en el medio de esa cantidad y preguntar si la solucion es mas grande que la mitad o mejor que la mitad, de esta forma vamos ir ajustando segun sea la solucion la cantidad de personas a mirar, es decir vamos agarrando la mitad del maximo de las personas y decidiendo si puedo transportar mas de esa cantidad o menos, segun el resultado es donde nos vamos a mover y finalmente ese resultado va a estar acotado por dos numeros, un valor minimo para la solucion y un maximo, si puedo transportar el maximo, entonces tenemos la solucion en el maximo, caso contrario, el minimo va a ser mi solucion. Esta función usa \textit{recheableCantPeople} para saber cuales de esta cantidad de personas nos sirve como posible solucion y para poder decidir si nos desplazamos hacia numeros mas grandes o mas chicos.
 \item  \textit{reachableCantPeople}: Esta función es un poco mas complicada, se encarga de, dado una cantidad x de personas, buscar si es posible alcanzarla, teniendo en cuenta la posibilidad de movimientos, es decir, teniendo en cuenta la energia, cuantas personas puedo cargar por piso, sabiendo la capacidad y el contenido del ascensor en todo momento. Por ejemplo si x = 10 y mi capacidad es menor, esta funcion me diria que no es posible alcanzar esa cantidad, por dar un ejemplo que busque clarar un poco la explicacion. Esta funcion tiene dos partes, que son \textit{GoDown} y \textit{GoUp}, tambien proveemos del pseudocodigo de los mismos.

\newpage

\begin{parr}
\begin{algorithm}[H]
\caption{\operL{maxPeople}{\vin{a}, \vin{b}}{int}}
\begin{algorithmic}[1]\parskip=1mm

\STATE resultado $\leftarrow$ 0
\STATE minPosibleSolution $\leftarrow$ a
\STATE maxPosibleSolution $\leftarrow$ b
\STATE mediumPosibleSolution $\leftarrow$ (minPosibleSolution + maxPosibleSolution)/2

	\IF{(Los pisos a los que puedo ir son, ninguno)}
		\STATE \textbf{return} $\leftarrow$ 0
	\ELSE
		\IF{(maxPosibleSolution $<$ maxPosibleSolution - 1)}
			\IF{(puedo alcanzar "mediumPosibleSolution" de gente)}
				\STATE recursion con maxPeople(mediumPosibleSolution, maxPosibleSolution) buscando agrandar el resultado
			\ELSE
				\STATE recursion hacia el otro lado, con maxPeople(minPosibleSolution, mediumPosibleSolution) buscamos achicarlo;
			\ENDIF
		\ENDIF

		\IF{(si puedo alcanzar "maxPosibleSolution" de gente)}
			\STATE el resultado va a ser la solucion maxima
		\ELSE
			\STATE entonces mi solucion va a ser la minima
		\ENDIF

	\ENDIF

\end{algorithmic}
\end{algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}[H]
\caption{\operL{reachableCantPeople}{ \vinout{cantidad}{int}}{boolean}}
\begin{algorithmic}[1]\parskip=1mm

\STATE acumuladoAbajo $\leftarrow$ 0
\STATE acumuladaArriba $\leftarrow$ 0
\STATE i $\leftarrow$ 0
\STATE lista $\leftarrow$ reachableFloors
\STATE peopleInElevator $\leftarrow$ 0
\STATE energiaDisponible $\leftarrow$ energia/2

\STATE  Arriba = \textbf{GoUp}($acumuladoAbajo$,$ i$, $lista$, $peopleInElevator$, $energiaDisponible$, $cantidad$);
			
\STATE /COMMENT{ Ahora busco desde lo mas arriba y voy bajando}
\STATE peopleInElevator $\leftarrow$ 0
\STATE lista $\leftarrow$ reachableFloors.clone() \COMMENT {A lista le asigno una copia de los posibles pisos}
\STATE i $\leftarrow$ lista.length;
\STATE energiaDisponible $\leftarrow$ energia/2;
		
\STATE \COMMENT {Tengo que buscar el minimo, porque voy a ir hasta lo mas arriba posible para empezar a descender}
		\IF {(lista.length < energiaDisponible)}
			\STATE i $\leftarrow$ lista.length - 1;
		\ELSE
			\STATE i $\leftarrow$ energiaDisponible - 1;
		\ENDIF
		
\STATE Abajo $\leftarrow$ textbf{GoDown}($acumuladoArriba$, $lista$, $peopleInElevator$,$ i$, $energiaDisponible$, $cantidad$)
\STATE \textbf{return} Abajo || Arriba ;

\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{\operL{GoDown}{ \vinout{acumuladoAbajo}{int},\vinout{lista}{int[]},\vinout{peopleInElevator}{int}.\vinout{i}{int}.\vinout{energiaDisponible}{int},\vin{cantidad}{int}}{boolean}}
\begin{algorithmic}[1]\parskip=1mm

\STATE \COMMENT {Calculo primero las posibilidades si empiezo desde abajo para arriba, subiendo gente solo en ascenso.}
	\WHILE[]{(acumuladoAbajo $<$ cantidad y i $<$ energiaDisponible)}
		\IF[]{(lista[i] $>=$ capacidad del elevador)}
			\IF{(Si lo que voy a buscar suma a lo que tengo, se me va de la cantidad)}
				\STATE lista[i] $\leftarrow$ cantidad - acumuladoAbajo \COMMENT {Le quito lo que necesito y actualiza esa pos}
				\STATE peopleInElevator $\leftarrow$ cantidad - acumuladoAbajo \COMMENT {Voy a tener lo que necesito.}
				\STATE acumuladoAbajo $\leftarrow$ cantidad
			\ELSE
				\STATE lista[i] $\leftarrow$  Lo que tenia en esa pos menos  lo maximo que peudo llevar, con lo que realmente estoy llevando
				\STATE acumuladoAbajo $\leftarrow$  lo mismo que estoy restando en esa posicion
				\STATE peopleInElevator $\leftarrow$ Capacidad del elevador \COMMENT {Ahora voy a tener el ascensor completo}
			\ENDIF
		\ELSE
			\IF{(si me estoy pasando de lo que me piden)}
				\STATE lista[i] $\leftarrow$  es lo que tenia menos la diferencia entre la cantidad y lo que hay en la lsita, es decir lo que me falta para que sea lo que me piden
				\STATE peopleInElevator $\leftarrow$  es lo que tenia mas lo que esta apuntando el indice actual en la lista
				\STATE acumuladAbajo $\leftarrow$  va a ser la cantidad qeu estoy buscando, ya que subo solo hasta esa cantidad.
			\ELSE
				\STATE acumuladoAbajo $\leftarrow$  es lo que tenia mas lo que esta en la lista apuntado por el indice actual
				\STATE peopleInElevator $\leftarrow$  le sumo lo que esta en la la lista, en el indice actual
				\STATE lista[i] $\leftarrow$  actualizo esta posicion restandole su misma cantidad y dejandolo en 0
			\ENDIF
		\ENDIF

		\IF{(si ya esta todo ocupado el ascensor)}
			\STATE peopleInElevator $\leftarrow$  va a ser 0, porque tengo que ir a planta baja a descargar
			\STATE energiaDisponible $\leftarrow$  va a ser lo que era menos uno mas al indice donde estoy, pues tiene que bajar y capaz tiene energia extra para subir
			\STATE i $\leftarrow$  0 pues, estoy en planta baja para poder dejar a la gente.
		\ELSE
			\STATE i $\leftarrow$  i + 1 sumo para seguir recorriendo la lista.
		\ENDIF

	\ENDWHILE

\STATE \textbf{return} (acumuladoArriba == cantidad)
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{\operL{GoDown}{ \vinout{acumuladoArriba}{int},\vinout{lista}{int[]},\vinout{peopleInElevator}{int}.\vinout{i}{int}.\vinout{energiaDisponible}{int},\vin{cantidad}{int}}{boolean}}
\begin{algorithmic}[1]\parskip=1mm

\STATE \COMMENT {Ahora tengo que recorrer desde el piso mas alto que me permite la energia hasta pb, subiendo gente para ver si de esta forma llego a la cantidad solicitad.}
\STATE \COMMENT {Para esto actualizo los valores necesarios que habia pisado en la cuenta ascendente.}

\IF{(la lista es mas grande que la energia disponible)}
	\STATE i $\leftarrow$ longitud de la lista - 1
\ELSE
	\STATE i $\leftarrow$ energiaDisponible -1
\ENDIF
		
	\WHILE[i igual al minimo entre longitud y energia]{(acumuladoArriba $<$ cantidad y  i $>=$ 0)}
		\IF[Miro de no querer subir mas gente de la puedo]{(lista[i] $>=$ capacidad del elevador)} 
			\IF[ Si puedo agarrar mas pero me paso de lo que quiero, agarro lo justo.]{acumuladoArriba $+$ espacio en el ascensor) $>$ cantidad)}
				\STATE lista[i] $\leftarrow$ cantidad - acumuladoArriba, le quito lo que necesito y actualiza esa pos
				\STATE peopleInElevator $\leftarrow$ cantidad - acumuladoArriba voy a tener lo que necesito.
				\STATE acumuladoAbajo $\leftarrow$ la cantidad, ya uqe estoy viendo que no me quiero pasar de eso.
			\ELSE
				\STATE lista[i] $\leftarrow$  va a ser lo que tenia en esa pos menos  lo maximo que peudo llevar, con lo qeu realmente estoy llevando
				\STATE acumuladoArriba $\leftarrow$  lo que tenia mas lo que estoy llevando en el ascensor
				\STATE peopleInElevator $\leftarrow$  ahora voy a tener el ascensor completo
			\ENDIF
		\ELSE
			\IF[Si lo que hay en el piso es menor pero es mas grande que mi cantidad]{(acumuladoArriba $+$ lista[i] $>$ cantidad)}
				\STATE lista[i] $\leftarrow$  lo que me falta para que sea lo que me piden.
				\STATE peopleInElevator $\leftarrow$  es lo que tenia mas lo que esta apuntando el indice actual en la lista
				\STATE acumuladoAbajo $\leftarrow$  va a ser la cantidad que estoy buscando, ya que subo solo hasta esa cantidad.
			\ELSE
				\STATE acumuladoArriba $\leftarrow$  es lo que tenia mas lo que esta en la lista apuntado por el indice actual
				\STATE peopleInElevator $\leftarrow$  le sumo lo que esta en la la lista, en el indice actual
				\STATE lista[i] $\leftarrow$  actualizo esta posicion restandole su misma cantidad y dejandolo en 0
			\ENDIF
		\ENDIF

		\IF{(si ya esta todo ocupado el ascensor)}
			\STATE peopleInElevator $\leftarrow$  va a ser 0, porque tengo que ir a planta baja a descargar
			\STATE energiaDisponible $-=$ i+1 \COMMENT {Pues puedo tener energia para volver a subir.}  
			\STATE i $\leftarrow$  energiaDisponible - 1 \COMMENT {Es decir es lo que me queda de energia - 1, para representar el indice en la lista.}
		\ELSE
			\STATE i $\leftarrow$  i - 1 \COMMENT {Resto para seguir bajando en la lista.}
		\ENDIF

	\ENDWHILE

\STATE \textbf{return} (acumuladoAbajo == cantidad)

\STATE \textbf{return} $\leftarrow$ acumuladoAbajo == cantidad || acumuladoArriba == cantidad
\STATE \COMMENT {Por cualquiera de las dos formas, voy a tener un camino, entonces devuelvo true si alguna pasa.}

\end{algorithmic}
\end{algorithm}
\end{parr}

\end{itemize}
\subsection{Desarrollo}

Para resolver este problema usamos una clase, para representar al elevador, con dos metodos para poder preguntarle su energia y su capacidad.\\
Lo primero que hacemos es crearnos un elevador con los datos que nos pasan, energia y la capacidad del elevador y buscar cuales son los pisos, del edifcio que me pasan, que realmente puedo llegar a alcanzar, es decir segun la cantidad de energia y la cantidad de pisos, me voy a quedar con los pisos del edifcio que puedo llegar a usar, para esto decidimos dividir la cantidad de energia por 2, ya que son los movimientos efectivos, o sea, solo contamos las veces que va a subir, sabiendo que si es un movimiento valido, siempre va a tener que volver a planta baja.\\

Tambien contamos la cantidad total de gente, pues la solucion final depende de la cantidad de gente total del edificio o por lo menos está superiormente acotada por esa cantidad, luego buscamos ajustar esta cota para encontrar la solucion mas optima, para esto, nos paramos en la mitad de la cantidad total y vamos a ir preguntando si puedo alcanzar mas gente o menos gente y segun este resultado iremos ajustando esta cantidad hasta tenerlo ajustado.\\
Entonces para esto vamos a usar las funciones que explicamos antes brevemente, calculamos segun la cantidad total de personas, su mitad, es decir vamos a guardarnos dos partes, el minimo de personas que puedo llegar a levantar y el maximo ( 0 y la cantidad total de personas, a priori, sin saber nada, eso puede pasar), sumamos estas dos partes y dividimos por dos, esto es muy parecido a una busqueda binaria, si no lo es, para encontrar el resultado mas optimo de personas que mi elevador es capaz de bajar. Entonces si es una posibilidad poder bajar la cantidad de gente calculada antes, busco poder bajar mas, si no era posible, busco bajar menos.\\
Para saber si el calculo de personas que hicimos antes es posible que sea una solucion, es decir, si es posible sabiendo la energia, la capacidad del ascensor y la disposicion en el edificio de esas personas, bajarlas a planta baja, hacemos uso de la funcion \textbf{reachableCantPeople}.
Entonces para saber si una posible solucion lo que calculamos antes, tenemos que ver si la energia y la capacidad del elevador es suficiente para hacer de ese calculo una solucion.
Para esto vamos a ir recorriendo el edificio empezando en planta baja y empezando en la planta mas alta posible segun la cantidad de energia (ya que al descender puede ir levantando gente), para realizar esta serie de cosas, tenemos que tener en cuenta si lo que queremos subir al ascensor es mas de lo que podemos (es mas grande que la capacidad o es mucho mas de lo que nos queda de lugar en el ascensor por tener mas gente adentro) e ir actualizando los lugares en el edificio donde subimos gente, ademas de ver si en alguna de las subidas o bajadas, nos sobro energia como para volver a subir y buscar mas gente, esto de subir y bajar, se va a regir por si el ascensor se lleno o no o si ya alcance la cantidad pedida, ya que una vez lleno tengo que bajar a toda la gente, fijarme la energia restante y en caso de tener un resto volver a subir a buscar mas gente, entonces puedo decir que , sí es posible esa cantidad que me pasaron.\\
Esto por cada cantidad de gente posible, a medida que voy encontrando un "camino" que me maximize la energia, voy a intentar aumentar la cantidad de gente hasta que no sea posible aumentar o disminuir mas la cantidad y solo me quede preguntar si el maximo de gente puedo llevar o si es el minimo de gente el que puedo transportar.



\subsubsection{Aclaraciones}
\begin{itemize}
  \item Intentamos una solucion con programacion dinamica, pero esto nos trajo muchos problemas y optamos por una solucion mas directa.
Esta implementacion termino siendo mas costosa a la hora de hacer el codigo y de su testeo, ya que era un poco larga de seguir, pero igualmente vimos que la funcion se portaba bien para el problema planteado.
\end{itemize}


\subsection{Complejidad}

El algoritmo usa la clase \textit{Elevator} que implementamos nosotros, que lo unico que hace es acomodarnos los datos, es decir son solo asignaciones a enteros y referencias.
Para analizar la complejidad de este algoritmo, vamos a calcular el costo temporal de las funciones anteriormente descriptas y una mas que no decidimos describir ya que lo unico que hace es preparnos bien los pisos que realmente valen la pena ser vistos y calcular el maximo de personas:\\


\begin{itemize}
 
 \item  $maxPeople$: Esta función toma el maximo de los pisos en base a los pisos validos, para esto, primero calculamos cuales son los pisos posibles a alcanzar, es decir, nos fijaamos al diferencia entre la cantidad de pisos y la energia/2, para ver si el ascensor tiene posibilidades de subir hasta el ultimo piso o solo llega hasta alguno anterior al ultimo, en base a esto calculamos el maximo de los pisos, recorriendo linealmente y quedandonos con el mayor, estas dos cosas tiene complejidad O(energia/2) y O(pisos) respectivamente.\\
Entonces maxPeople lo que va a hacer es usar este maximo y un minimo que se iniciliaza siempre en 0, hacemos el calculo de sumar estos dos y dividir por dos, esto por cada recursion que hacemos, entonces como siempre voy a tener el "maximo" y el "minimo" por cada recursion, esto es muy parecido al logaritmo de la cantidad de personas maximas en todo el edificio, ya que siempre vamos a estar dividiendo estas cantidades a la mitad y ademas, como el resto son ifs con comparaciones entre enteros (O(1)) concluimos que la complejidad de esta funcion es O(log(maxPersonas)), donde maxPersonas es la cantidad maxima de personas en todo el edificio.\\
 \item  $reachableCantPeople$: Esta función es un poco mas complicada de analizar a simple vista, pero no es tan complicada si se analiza con cuidado.\\
Las primeras lineas son solo declaraciones e inicializaciones de variables no mas complicadas que enteros pero si tenemos una asignacion un poco mas compleja, que es la asignacion de la lista, que necesitamos que sea por copia, esto es de costo igual a la longitud de mi otra lista que es reachableFloors entonces esto es de orden O(pisos) como mucho ya que si no pudimos filtrar los pisos por ser mas chicos o igual a la energia que nos dice el enuncia, entonces, su peor caso, es que los pisos alcanzables sean iguales a los pisos originales, al momento del while(esto es ya metiendonos en la complejidad de \textit{GoUP}, tenemos que la guarda depende de la cantidad a ser analizada y de la energia disponible, es decir el acumuladoAbajo tiene como "tope" la cantidada a analizar y el entero i tiene como "tope" la cantidad de energiaDisponible, a priori la complejidad de esta guarda solamente podria ser el mas grande entre cantidad y energiaDisponible, pero si vemos mas atentamente, podemos pensar que en peor caso, uno puede recorrer toda la lista pues si la energia es suficiente como para hacerlo, puede que uno recorra todo y no encuentre esa cantidad, entonces concluimos que la complejidad de esta guarda es O(energia). Luego dentro de este while tenemos muchos ifs, con asignaciones, comparaciones y restas-sumas. Si miramos bien las lineas que encierra el while, nos damos cuenta que son solo eso, comparaciones, asignaciones y operaciones aritmeticas entre enteros no muy costosas, es decir son de costo constantes (O(1)).\\
Resumiendo, hasta aca tenemos una creacion de de una lista O(pisos) + O(energia) por el while.\\
Ahora tenemos el segundo while ya en la parte de la funcion \textit{GoDown}, pero antes nos vuelve a pasar lo mismo que al principio, la creacion o el "clonaje" de una lista, esto nos vuelve a costar O(pisos), luego si, tenemos la guarda del while que vuelve a depender de la cantidad a analizar y de los pisos o de la energia, esto no se ve muy claro, pero como estamos mirando hacia atras, es decir estamos seteando a i como la cantidad de pisos o la energiaDisponible, segun quien es mas chico y vamos a ir bajando el valor de i, entonces podemos concluir que esto es el min(energia,piso). Entonces tenemos O(pisos) + min(energia,piso).\\
Luego al igual que en el primer while, tenemos muchos ifs pero con comparaciones y asignaciones entre enteros, es por eso que la parte de "adentro" del while la consideramos constante (O(1)). Por ultimo tenemos el resultado, que es una comparacion entre enteros y un o lógico, esto es O(1).\\
Finalmente, con todo ya calculado, podemos decir que como por cada vez que usamos $maxPeople$ llamamos a $reachableCantPeople$, o sea esto seria

\item log(maxPersonas)*(O(pisos)+O(energia)+O(pisos)+O(min(energia,pisos))) $\in$ log(maxPersonas)*(O(pisos)+O(energia)) ya que 
\item O(pisos)+O(pisos) = 2*O(pisos) $\in$ O(pisos) y como min(energia,pisos) puede ser o O(energia) u O(pisos), podemos usar el mismo argumento anterior.\\
\\
 Es por esto que concluimos que nuestro algoritmo tiene complejidad asintotica 
\item O(log(maxPersonas)*(O(pisos)+O(energia)).
\\

\end{itemize}

\subsection{Tests}
Decidimos hacer un test aleatorio en el cual la capacidad y energía eran fijas como la mitad de tests que íbamos a hacer. De este modo, habría instancias en las que la capacidad y la energía son mayores que la cantidad de pisos y otra mitad de instancias en lo que pasaría exactamente lo contrario.
La cantidad de personas por piso era una variable entre 0 y cantidad de pisos * (1+(i*i)\%i). De esta manera podríamos generar instancias con una gran varianza entre las cantidades de personas por piso.
Tuvimos unos problemas el día de la entrega y no alcanzamos a entregar los gráficos de comparación ya que genera mal y era incosistente.

\subsection{Conclusiones}

En este problema, pudimos ver la complejidad de tratar con problemas en los que uno puede usar subsoluciones para calcular su solucion final, mas aun si no se implementa por programacion dinamica, esto un poco lo que nos paso, por no poder resolver este problema con este metodo, se nos hizo mas costoso y hasta mas extenso en su implementacion. 
Nos queda el aprendizaje de la importancia de la deteccion de un problema el cual se puede resolver con programacion dinamica, por su comoda implementacion (o por lo menos una forma mas sencilla de hallar una solucion, ya que, uno deberia saber como accionar y qué pasos seguir para resolver un caso de este tipo) es por eso que aunque no hayamos podido hacerlo de esta forma, implementandola de otra manera nos damos cuenta de la importancia de este metodo de resolucion de ciertos ejercicios a la hora de claridad y complejidad en la implementacion del codigo. 